// var searchInsert = function(nums, target) {
//     let left=0,right=nums.length-1

//     while(left<=right){
//         let mid=parseInt((left+right)/2)

//         if(target>nums[mid]){
//             left=mid+1
//         }else if(target<nums[mid]){
//             right=mid-1
//         }else{
//             // 找到了直接返回
//             return mid
//         }
//     }

//     // 找不到进行插入有如下三种情况
//     /*
//         target比所有元素都小，此时循环结束[left,right]=[0,-1]应该return right+1
//         target比所有元素都大，[left,right]=[length,length-1]应该return right+1
//         target在数组中间,最后一次循环left=right=mid：
//             最后一次循环left=right，若target比mid大，left=mid+1 此时left就是插入位置 return right+1
//             最后一次循环left=right，若target比mid小，right=mid-1 此时left还是插入位置 return right+1
//     */

//     return right+1
// };

var searchInsert = function(nums, target) {
    let left=0,right=nums.length

    while(left<right){
        let mid=parseInt((left+right)/2)

        if(target>nums[mid]){
            left=mid+1
        }else if(target<nums[mid]){
            right=mid
        }else{
            // 找到了直接返回
            return mid
        }
    }

    // 找不到进行插入有如下三种情况
    /*
        target比所有元素都小，此时循环结束[left,right)=[0,0)应该return right
        target比所有元素都大，[left,right]=[length,length)应该return right
        target在数组中间,最后一次循环left=right=mid：
            最后一次循环left=right-1，若target比mid大，left=mid+1 此时left就是插入位置 return right
            最后一次循环left=right-1，若target比mid小，right=mid-1 此时left还是插入位置 return right
    */

    return right
};

console.log(searchInsert([1,2,3,4],3.5));